| 翻訳と辞書 |
| List ranking ： ウィキペディア英語版 |
List ranking
In parallel algorithms, the list ranking problem involves determining the position, or rank, of each item in a linked list. That is, the first item in the list should be assigned the number 1, the second item in the list should be assigned the number 2, etc. Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel. As wrote, the problem was viewed as important in the parallel algorithms community both for its many applications and because solving it led to many important ideas that could be applied in parallel algorithms more generally.
==History==
The list ranking problem was posed by , who solved it with a parallel algorithm using logarithmic time and O(''n'' log ''n'') total steps (that is, O(''n'') processors). Over a sequence of many subsequent papers, this was eventually improved to linearly many steps (O(''n''/log ''n'') processors), on the most restrictive model of synchronous shared-memory parallel computation, the exclusive read exclusive write PRAM (; ;). This number of steps matches the sequential algorithm.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「List ranking」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|